package com.cat.dynamicPlanning;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/burst-balloons/description/
 * @create 2025/9/6 16:05
 * @since JDK17
 */

public class Solution87 {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        int[] arr = new int[n + 2];
        arr[0] = arr[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            arr[i + 1] = nums[i];
        }
        int[][] dp = new int[n + 2][n + 2];
        for (int i = 1; i <= n; i++) {
            dp[i][i] = arr[i] * arr[i - 1] * arr[i + 1];
        }
        for (int i = n; i > 0; i--) {
            for (int j = i + 1; j <= n; j++) {
                dp[i][j] = Math.max(arr[i] * arr[i - 1] * arr[j + 1] + dp[i + 1][j], arr[i - 1] * arr[j] * arr[j + 1] + dp[i][j - 1]);
                for (int k = i + 1; k < j; k++) {
                    dp[i][j] = Math.max(dp[i][j], arr[i - 1] * arr[k] * arr[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
                }
            }
        }

        return dp[1][n];
    }
}
